package com.fub.guidance;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

import android.util.Log;

public class DijkstraAlgorithm {

	private static final String DEBUG_TAG = "Dijkstra";
	private final List<Edge> edges;
	private Set<String> settledNodes;
	private Set<Vertex> unSettledNodes;
	private Map<Vertex, Vertex> predecessors;
	private Map<Vertex, Integer> distance;
	private Graph graph;

	/**
	 * Constructs an new Class for calculating the shortest path.
	 * 
	 * @param edges
	 *            the edges of the graph
	 */
	public DijkstraAlgorithm(List<Edge> edges) {
		this.graph = Graph.getInstance();
		this.edges = edges;
		ArrayList<Edge> newedges = new ArrayList<Edge>();
		for (Edge edge : edges) {
			Edge reverse = new Edge(edge.getId() + "r", edge.getBuildingId(),
					edge.getDestinationId(), edge.getSourceId(),
					edge.getWeight());
			newedges.add(reverse);
		}
		this.edges.addAll(newedges);
	}

	/**
	 * Calculates the distance from source to all edges.
	 * 
	 * @param source
	 *            the source.
	 */
	public void execute(Vertex source) {
		long startExecuteTime = System.currentTimeMillis();
		this.settledNodes = new HashSet<String>();
		this.unSettledNodes = new HashSet<Vertex>();
		this.distance = new HashMap<Vertex, Integer>();
		this.predecessors = new HashMap<Vertex, Vertex>();
		this.distance.put(source, 0);
		this.unSettledNodes.add(source);
		while (this.unSettledNodes.size() > 0) {
			Vertex node = getMinimum(this.unSettledNodes);
			this.settledNodes.add(node.getId());
			this.unSettledNodes.remove(node);
			findMinimalDistances(node);
		}
		long endExecuteTime = System.currentTimeMillis();
		Log.d(DEBUG_TAG, "Berechnungsdauer:"
				+ (endExecuteTime - startExecuteTime));
	}

	/**
	 * Returns the path from the source to the selected target and NULL if no
	 * path exists.
	 * 
	 * @param target
	 *            the selected target
	 * @return the nodes of the shortest path
	 */
	public LinkedList<Vertex> getPath(Vertex target) {
		LinkedList<Vertex> path = new LinkedList<Vertex>();
		Vertex step = target;
		if (this.predecessors.get(step) == null) {
			return null;
		}
		path.add(step);
		while (this.predecessors.get(step) != null) {
			step = this.predecessors.get(step);
			path.add(step);
		}
		Collections.reverse(path);
		return path;
	}

	private void findMinimalDistances(Vertex node) {
		List<Vertex> adjacentNodes = getNeighbors(node);
		for (Vertex target : adjacentNodes) {
			if (getShortestDistance(target) > getShortestDistance(node)
					+ getDistance(node, target)) {
				this.distance.put(target, getShortestDistance(node)
						+ getDistance(node, target));
				this.predecessors.put(target, node);
				this.unSettledNodes.add(target);
			}
		}

	}

	private int getDistance(Vertex node, Vertex target) {

		for (Edge edge : node.getEdges()) {
			if (edge.getSourceId().equals(target.getId())
					|| (edge.getDestinationId().equals(target.getId()))) {
				return edge.getWeight();
			}
		}
		throw new RuntimeException("No way beetween" + node.getLabel()
				+ " and " + target.getLabel());
	}

	List<Vertex> neighbors = new ArrayList<Vertex>();

	private List<Vertex> getNeighbors(Vertex node) {
		this.neighbors.clear();
		for (Edge edge : node.getEdges()) {
			if (!edge.getSourceId().equals(node.getId())) {
				this.neighbors.add(this.graph.getNodeById(edge.getSourceId()));
			} else {
				this.neighbors.add(this.graph.getNodeById(edge
						.getDestinationId()));
			}
		}
		return this.neighbors;
	}

	private Vertex getMinimum(Set<Vertex> vertexes) {
		Vertex minimum = null;
		for (Vertex vertex : vertexes) {
			if (minimum == null) {
				minimum = vertex;
			} else {
				if (getShortestDistance(vertex) < getShortestDistance(minimum)) {
					minimum = vertex;
				}
			}
		}
		return minimum;
	}

	private int getShortestDistance(Vertex destination) {
		Integer d = this.distance.get(destination);
		if (d == null) {
			return Integer.MAX_VALUE;
		} else {
			return d;
		}
	}
}
